package sieve;

import java.util.BitSet;

public class Sieve {
    public static void main(String[] args) {
        int n = 2000000;

        long start = System.currentTimeMillis();

        var bitSet = new BitSet(n+1);

        // 假设大于等于2的都是素数
        bitSet.flip(2, n+1);

        for (int i = 2; i * i <= n; i++) {
            // 如果i是素数
            if (bitSet.get(i)) {
                // i*(i+...)的都是合数
                for (int j = i * i; j <= n; j += i) {
                    bitSet.clear(j);
                }
            }
        }

        long end = System.currentTimeMillis();

        System.out.println(bitSet.cardinality() + " primes");
        System.out.println((end-start) + " milliseconds");
    }
}
